
List<List<int>> createSourceData() {
  // final sourceData = <List<int>>[];
  // for (var i = 0; i < 9; i++) {
  //   final row = <int>[];
  //   for (var j = 0; j < 9; j++) {
  //     row.add(0);
  //   }

  //   sourceData.add(row);
  // }
  // return sourceData;
  // return <List<int>>[
  //   [0, 0, 2, 0, 0, 6, 3, 0, 9],
  //   [3, 9, 0, 0, 2, 0, 1, 7, 0],
  //   [0, 1, 0, 7, 9, 3, 0, 0, 0],
  //   [1, 4, 0, 0, 3, 9, 0, 0, 0],
  //   [0, 0, 0, 4, 0, 0, 0, 6, 1],
  //   [9, 2, 0, 0, 8, 0, 0, 0, 0],
  //   [0, 0, 4, 0, 0, 8, 7, 9, 0],
  //   [0, 0, 9, 0, 0, 0, 8, 1, 0],
  //   [8, 0, 1, 9, 0, 0, 0, 2, 0],
  // ];

  // 模板数据
  // return <List<int>>[
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  //   [0, 0, 0, 0, 0, 0, 0, 0, 0],
  // ];
  // return <List<int>>[
  //   [0, 4, 0, 5, 0, 0, 8, 0, 0],
  //   [0, 9, 0, 0, 8, 0, 0, 0, 7],
  //   [0, 2, 6, 0, 0, 3, 0, 9, 0],
  //   [0, 3, 9, 0, 0, 0, 5, 1, 0],
  //   [1, 0, 0, 3, 6, 5, 0, 0, 0],
  //   [7, 0, 0, 0, 0, 4, 2, 0, 3],
  //   [0, 0, 0, 0, 5, 0, 0, 7, 4],
  //   [2, 0, 0, 6, 3, 0, 0, 0, 0],
  //   [9, 0, 3, 4, 0, 0, 0, 0, 8],
  // ];
  return <List<int>>[
    [0, 0, 4, 0, 0, 0, 2, 0, 5],
    [8, 0, 0, 0, 0, 0, 0, 0, 3],
    [6, 0, 7, 8, 0, 0, 0, 0, 0],
    [7, 1, 0, 0, 0, 3, 0, 0, 0],
    [0, 6, 0, 0, 0, 0, 3, 0, 0],
    [0, 0, 0, 5, 2, 0, 0, 0, 1],
    [0, 0, 2, 0, 0, 6, 0, 4, 0],
    [0, 0, 0, 7, 0, 0, 9, 0, 0],
    [0, 3, 6, 0, 1, 0, 0, 0, 0],
  ];
}

class ShuDu {
  String title = '数独';
  String subTitle;
  final List<List<int>> _sourceData;

  ShuDu(this._sourceData) : assert(_sourceData != null) {
    _initSourcePoints();
  }

  final Map<int, Point> _sourcePoints = {};
  int totalLoopCount = 0;
  int _emptyLoopCount = 0;
  // 获取
  List<List<int>> get currentData {
    final result = <List<int>>[];
    for (var y = 1; y <= 9; y++) {
      final rowValueList = <int>[];
      for (var x = 1; x <= 9; x++) {
        rowValueList.add(_sourcePoints[(y - 1) * 9 + x].value);
      }
      // print(rowValueList);
      result.add(rowValueList);
    }
    return result;
  }

  // 初始化
  void _initSourcePoints() {
    var x = 1; // column
    var y = 1; // row
    for (var row in _sourceData) {
      for (var item in row) {
        _sourcePoints[x + (y - 1) * 9] = Point(x, y, value: item);
        x++;
      }
      y++;
      x = 1;
    }
  }

  // 打印矩阵
  void printPoints() {
    if (_sourcePoints.length != 81) {
      print('数量不对');
      return;
    }

    print(title + (subTitle ?? ''));
    for (var y = 1; y <= 9; y++) {
      final rowValueList = [];
      for (var x = 1; x <= 9; x++) {
        rowValueList.add(_sourcePoints[(y - 1) * 9 + x].value);
      }
      print(rowValueList);
    }
  }

  static const valueSet = {1, 2, 3, 4, 5, 6, 7, 8, 9};

  /// 获取行上点的集合
  List<Point> _getRowPointList(int row) {
    final rowPointList = <Point>[];
    for (var i = 1; i <= 9; i++) {
      var _index = row * 9 + i;
      rowPointList.add(_sourcePoints[_index]);
    }
    return rowPointList;
  }

  /// 获取列上点的列表
  List<Point> _getColumnPointList(int column) {
    final columnPointList = <Point>[];
    for (var row = 0; row < 9; row++) {
      var _index = row * 9 + column + 1;
      columnPointList.add(_sourcePoints[_index]);
    }
    return columnPointList;
  }

  /// 获取网格上点的集合
  List<Point> _getGridPointList(int index) {
    final gridPointList = <Point>[];
    var startRow = index ~/ 3 * 3;
    var startColumn = index % 3 * 3;

    for (var row = startRow; row < startRow + 3; row++) {
      for (var column = startColumn; column < startColumn + 3; column++) {
        var _index = row * 9 + column + 1;
        gridPointList.add(_sourcePoints[_index]);
      }
    }
    return gridPointList;
  }

  // /// 获取行的值集合
  // Set<int> getRowValueSet(int row) {
  //   return getRowPointList(row).map((point) => point.value).toSet();
  // }

  // /// 获取列的值集合
  // Set<int> getColunmValueSet(int column) {
  //   return getColumnPointList(column).map((point) => point.value).toSet();
  // }

  // /// 获取单元格的值集合
  // Set<int> getGridRemainValue(int index) {
  //   return getGridPointSet(index).map((point) => point.value).toSet();
  // }

  /// 依据相关行、列、单元格中已确定的值，计算每个点的可能值集合
  void _calculateEveryPointMaybeValueSet() {
    final rowValueSetList = <Set<int>>[];
    final columnValueSetList = <Set<int>>[];
    final gridValueSetList = <Set<int>>[];
    for (var i = 0; i < 9; i++) {
      rowValueSetList
          .add(_getRowPointList(i).map((point) => point.value).toSet());
      columnValueSetList
          .add(_getColumnPointList(i).map((point) => point.value).toSet());
      gridValueSetList
          .add(_getGridPointList(i).map((point) => point.value).toSet());
    }

    // print(rowRemainValueSetList);
    // print(columnRemainSetList);
    // print(gridRemainValueSetList);

    _sourcePoints.forEach((key, item) {
      if (item.isConst || item.isFinished) {
        return;
      }
      var rowValueSet = rowValueSetList[item.y - 1];
      var columnValueSet = columnValueSetList[item.x - 1];
      var gridValueSet = gridValueSetList[item.gridIndex - 1];
      var maybeValueSet = valueSet
          .difference(rowValueSet.union(columnValueSet).union(gridValueSet));

      item.rowValueSet = rowValueSet;
      item.columnValueSet = columnValueSet;
      item.gridValueSet = gridValueSet;
      item.maybeValueSet = maybeValueSet;

      // print('计算 $item 的可能值');
      // print('rowValueSet $rowValueSet');
      // print('columnValueSet $columnValueSet');
      // print('gridValueSet $gridValueSet');
      // print('maybeValueSet $maybeValueSet');
      // print('计算后的 $item');
    });
  }

  // 更新已确定的点上面的值
  void _updatePointValue() {
    _sourcePoints.forEach((key, item) {
      if (!item.isConst && !item.isFinished) {
        if (item.maybeValueSet.length == 1) {
          _emptyLoopCount = 0;
          print('更新 $item');
          item.value = item.maybeValueSet.first;
          // print('rowValueSet ${item.rowValueSet}');
          // print('columnValueSet ${item.columnValueSet}');
          // print('gridValueSet ${item.gridValueSet}');

        } else if (item.checkMaybeValueSet?.length == 1) {
          _emptyLoopCount = 0;
          print('更新 $item');
          item.value = item.checkMaybeValueSet.first;
          // print('rowValueSet ${item.rowValueSet}');
          // print('columnValueSet ${item.columnValueSet}');
          // print('gridValueSet ${item.gridValueSet}');
          print('checkMaybeValueSet ${item.checkMaybeValueSet}');
        }
        item.maybeValueSet = null;
        item.rowValueSet = null;
        item.columnValueSet = null;
        item.gridValueSet = null;
        // item.checkMaybeValueSet = null;
      }
    });
  }

  // 检查是否完成(找到了所有的值)
  bool _checkFinish() {
    return _sourcePoints.values.every((value) => value.value != 0);
  }

  // 计算结果
  bool calculateResult() {
    printPoints();

    /// 获取每个点可能的值
    _calculateEveryPointMaybeValueSet();
    while (!_checkConflict() && !_checkEmptyLoop()) {
      totalLoopCount++;
      _emptyLoopCount++;

      print('第$totalLoopCount轮');
      for (var i = 0; i < 81; i++) {
        _checkPointWithIndex(i);
      }

      _updatePointValue();
      _calculateEveryPointMaybeValueSet();
    }

    print('loop: $totalLoopCount');
    printPoints();
    // for (var i = 1; i <= 81; i++) {
    //   print(sourcePoints[i]);
    // }

    if (_checkConflict()) {
      print('发现冲突');
      return false;
    }

    if (_checkFinish()) {
      print('完成');
      return true;
    }

    return _tryMaybeValue();
  }

  // 尝试可能的值
  bool _tryMaybeValue() {
    final maybePointList = _sourcePoints.values.where((item) {
      if (item.maybeValueSet != null) {
        return item.maybeValueSet.length > 1;
      }
      return false;
    }).toList();
    // print(maybePointList);

    for (var maybePoint in maybePointList) {
      final x = maybePoint.x;
      final y = maybePoint.y;
      final maybeValueList = maybePoint.maybeValueSet.toList();
      for (var maybeValue in maybeValueList) {
        final _data = currentData;
        _data[y - 1][x - 1] = maybeValue;

        final maybeShudu = ShuDu(_data);
        maybeShudu.totalLoopCount = totalLoopCount;
        final _str = '(假设 $maybePoint 为 $maybeValue)';
        maybeShudu.subTitle = subTitle == null ? _str : subTitle + _str;
        print('============${maybeShudu.subTitle}===========');

        if (maybeShudu.calculateResult()) {
          return true;
        } else {
          print('========假设 $maybePoint 为 $maybeValue 不成立========');
        }
      }
    }
    return false;
  }

  // 通过其他相关位置的点的可能值来进一步排除
  void _checkPointWithIndex(int index) {
    final currentPoint = _sourcePoints[index + 1];
    if (currentPoint.isConst || currentPoint.isFinished) {
      return;
    }
    // 获取行上的点
    final row = index ~/ 9;
    final rowPointList = _getRowPointList(row);
    _updatePointCheckMaybeValue(currentPoint, rowPointList);
    // 获取列上的点
    final column = index % 9;
    final columnPointList = _getColumnPointList(column);
    _updatePointCheckMaybeValue(currentPoint, columnPointList);
    // 获取网格上的点
    final gridPointList = _getGridPointList(currentPoint.gridIndex - 1);
    _updatePointCheckMaybeValue(currentPoint, gridPointList);
  }

  // 更新排查可能值
  void _updatePointCheckMaybeValue(Point targetPoint, List<Point> pointList) {
    // 当前集合所有剩余填充的值，和maybeValue的集合相同
    // final allRemainValueSet = <int>{};
    // pointList.forEach((item) {
    //   if (item.isConst || item.isFinished) {
    //     return;
    //   }
    //   allRemainValueSet.addAll(item.checkMaybeValueSet ?? item.maybeValueSet);
    // });
    // final allRemainValueSet =
    // valueSet.difference(pointList.map((point) => point.value).toSet());

    pointList.remove(targetPoint);
    final otherPointMaybeValueSet = <int>{};
    pointList.forEach((point) {
      if (point.isConst || point.isFinished) {
        return;
      }
      otherPointMaybeValueSet
          .addAll(point.checkMaybeValueSet ?? point.maybeValueSet);
    });

    // for (var j = 0; j < pointList.length; j++) {
    //   if (j != i) {
    //     final otherPoint = pointList[j];
    //     if (otherPoint.isConst || otherPoint.isFinished) {
    //       continue;
    //     }
    //     otherPointMaybeValueSet.addAll(otherPoint.maybeValueSet);
    //     if (otherPoint.maybeValueSet.length > 1) {}
    //   }
    // }

    final targetCheckMaybeValueSet =
        targetPoint.checkMaybeValueSet ?? targetPoint.maybeValueSet;
    final checkMaybeValueSet =
        targetCheckMaybeValueSet.difference(otherPointMaybeValueSet);

    if (checkMaybeValueSet.length == 1) {
      // print(targetPoint);
      // print('check $targetPoint');
      // print('checkMaybeValue $checkMaybeValueSet');
      // print('allRemainValueSet $allRemainValueSet');
      // print('otherPointMaybeValueSet $otherPointMaybeValueSet');
      // print('rowValueSet ${targetPoint.rowValueSet}');
      // print('columnValueSet ${targetPoint.columnValueSet}');
      // print('gridValueSet ${targetPoint.gridValueSet}');
      // print('maybeValueSet ${targetPoint.maybeValueSet}');
      // targetPoint.maybeValueSet = maybeValue;
      targetPoint.checkMaybeValueSet = checkMaybeValueSet;
    }
  }

  // 检查是否有冲突
  bool _checkConflict() {
    var result = false;
    for (var i = 0; i < 9; i++) {
      if (result == true) return true;
      final fList = [
        _getRowPointList,
        _getColumnPointList,
        _getGridPointList,
      ];
      fList.forEach((f) {
        final pointList = f(i)
            .where((point) => point.value != 0)
            .map((point) => point.value);
        final valueList = pointList.toList();
        final valueSet = pointList.toSet();
        if (valueList.length != valueSet.length) {
          result = true;
        }
      });
    }
    return false;
  }

  // 检查是否无法找到确定的值
  bool _checkEmptyLoop() {
    return _emptyLoopCount > 0;
  }
}

class Point {
  final int x; // 从1开始
  final int y; // 从1开始
  final bool isConst;
  bool _isFinished = false;
  bool get isFinished => _isFinished;

  int _value;
  int get value {
    return _value;
  }

  set value(int value) {
    if (isConst) {
      print('尝试更新初始数据 $this');
      return;
    }

    _isFinished = true;
    _value = value;
  }

  Set<int> maybeValueSet;
  Set<int> rowValueSet;
  Set<int> columnValueSet;
  Set<int> gridValueSet;
  Set<int> checkMaybeValueSet;

  Point(this.x, this.y, {int value})
      : _value = value ?? 0,
        isConst = value != 0;

  String get _valueStr {
    return value == 0 ? maybeValueSet.toString() : value.toString();
  }

  @override
  String toString() {
    return 'Point($x,$y): ${_valueStr}';
  }

  int get gridIndex {
    //从1开始
    return (x - 1) ~/ 3 + (y - 1) ~/ 3 * 3 + 1;
  }
}
